﻿#include"map.h"
#include<vector>
#include<set>
#include <map>
#include <deque>
#include<iostream>
using namespace std;
CMyGraph::CMyGraph(void)
{
	float g[8][8] = {
	{ 0,12,	1,	0,	0,	0,	0,	4 },
	{ 12,0,	0,11,0,	10,	0,	0 },
	{ 1,0,0,9, 2, 0, 0, 0 },
	{ 0, 11, 9, 0, 0, 0, 8, 0 },
	{ 0, 0, 2, 0, 0, 0, 5, 3 },
	{ 0,10,	0,0,0,0,7,6 },
	{ 0,0,0,8,5,7,0,0 },
	{ 4,0,0,0,3,6,0,0 }
	};

	for (int i = 0; i < 8; i++)
	{
		SGNode sg;
		sg.key = i;
		NodeSet.push_back(sg);
	}
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if (g[i][j] != 0)
			{
				NodeSet[i].neighNodes.insert(map<int, float>::value_type(j, g[i][j]));
			}
		}
	}
	vector<SGNode>::iterator iter;
	for (iter = NodeSet.begin(); iter != NodeSet.end(); iter++)
	{
		cout << (*iter).key;
		map<int, float>::iterator iter2;
		for (iter2 = (*iter).neighNodes.begin(); iter2 != (*iter).neighNodes.end(); iter2++) {
			cout << ",(" << (*iter2).first << ", " << (*iter2).second << ")";

		}
		cout << endl;
	}
}
CMyGraph::~CMyGraph(void){}
void CMyGraph::DFS()
{
	bool *visited;
	visited = new bool[8];
	for (int i = 0; i < 8; i++) 
		visited[i] = false;
	vector<int> mystack; 
	DFS(0, mystack, visited);
}
void CMyGraph::DFS(int i, vector<int>& mystack, bool * visited)
{
	if (i >= 0 && i < NodeSet.size())
	{
		if (!visited[i])
		{
			cout << i << "\n";
			mystack.push_back(i);
			visited[i] = true;
		}

		map<int, float>::iterator iter;
		for (iter = NodeSet[i].neighNodes.begin(); iter != NodeSet[i].neighNodes.end(); iter++)
		{
			if (!visited[(*iter).first])
				DFS((*iter).first,mystack,visited);//递归
		}
		if (iter == NodeSet[i].neighNodes.end())
		{
			if (mystack.size() > 0)
			{
				mystack.pop_back();
				if (mystack.size() > 0)
					DFS(mystack.at(mystack.size() - 1), mystack, visited);//递归
			}
		}
	}
}

void CMyGraph::BFS()
{
	bool *visited;
	visited = new bool[8];

	for (int i = 0; i < 8; i++)
		visited[i] = false;
	deque<int> mydeque;
	BFS(0, mydeque, visited);

}
void CMyGraph::BFS(int i, deque<int>& mydeque, bool* visited)
{
	if (!visited[i])
	{
		cout << i << "/n";
		for (map<int, float>::iterator iter = NodeSet[i].neighNodes.begin(); iter != NodeSet[i].neighNodes.end(); iter++)
		{
			if (!visited[(*iter).first])
				mydeque.push_back((*iter).first);
		}
		visited[i] = true;
	}
	while (mydeque.size() > 0)
	{
		int i = mydeque.at(0);
		mydeque.pop_front();
		BFS(i, mydeque,visited);//递归
	}
}

void CMyGraph::Prim()
{
	//选择图中的任一顶点作为起点
	int start = 0;
	int s1;
	set<int> mtSet;
	mtSet.insert(start); // 选择初始节点
	float weight;
	while (1)
	{
		weight = 100000.0f; //人为设定较大值
		start = -1;
		s1 = -1;
		for (set<int>::iterator iter = mtSet.begin(); iter != mtSet.end(); iter++)
		{
			map<int, float>::iterator curlter = NodeSet[(*iter)].neighNodes.begin();
			while (curlter != NodeSet[(*iter)].neighNodes.end())
			{
				//当前节点己经在集合中
				if (mtSet.end() != (mtSet.find((*curlter).first)))
				{
					curlter++;
					continue;
				}
				//当前节点不在集合中，记录该节点并作为备选节点
				if ((*curlter).second < weight) //选择权重最小的边所边接的节点
				{
					s1 = (*iter);
					start = (*curlter).first;
					weight = (*curlter).second;
				}
				curlter++;
			}
		}
		if (-1 != start)
		{
			//从备选边与节点加入到最小生成树中
			mtSet.insert(start);
			cout<<"("<< s1<< "," << start<< ")"<< endl;
			if (mtSet.size() == NodeSet.size()) break;
		}
	}
}
void CMyGraph::Kruskal()
{
	//对所有边进行排序
	EdgeSet es;
	for (int i = 0; i < NodeSet.size(); i++)
	{
		for (map<int, float>::iterator iter = NodeSet[i].neighNodes.begin(); iter != NodeSet[i].neighNodes.end(); iter++)
		{
			if ((*iter).second !=0.0f)
			{
				SGEdge sg;
				sg.start = i;
				sg.end = (*iter).first;
				es.insert(EdgeSet::value_type((*iter).second, sg));
			}
		}
	}
	set<int> mtSet;
	//依次加入权重最小的边(数目：顶点数一1)
	EdgeSet::iterator iter = es.begin();
	for (int i = 0; i < NodeSet.size() - 1;)
	{
		//初始最小生成树为空的情况
		if (mtSet.size() == 0)
		{
			cout << "(" << (*iter).second.start;
			cout << ",";
			cout << (*iter).second.end << ")" << endl;
			mtSet.insert((*iter).second.start);
			mtSet.insert((*iter).second.end);
			iter++;
			i++;
			continue;
		}
		//待加入边的两个端点位于两个不同的子图中
		if ((mtSet.find((*iter).second.start) == mtSet.end() && mtSet.find((*iter).second.end) != mtSet.end() )||
			(mtSet.find((*iter).second.start) != mtSet.end() && mtSet.find((*iter).second.end) == mtSet.end()))
		{
		cout << "(" << (*iter).second.start;
		cout << ",";
			cout<<(*iter).second.end << ")" << endl;
		mtSet.insert((*iter).second.start);
		mtSet.insert((*iter).second.end);
		iter++;
		i++;
			}
		else 
		{
			iter++;
		}
		}
	}




	

